package recursion;

import java.util.Arrays;

/**
 * @author czt
 * @version 1.0
 * @since 2024/12/13
 *
 * 斐波那契数列，青蛙跳阶、兔子生兔子问题(从第三项开始，均为前两项之和)
 */
public class Fibonacci {

    public static void main(String[] args) {
        int fibonacci = fibonacci(3);
        System.out.println("fibonacci = " + fibonacci);
    }

    public static int fibonacci(int n) {
        if (n == 0) {
            return 0;
        }else if (n == 1) {
            return 1;
        } else if (n > 1) {
            return fibonacci(n - 1) + fibonacci(n - 2);
        } else {
            throw new RuntimeException("输入的n不合法");
        }
    }

    /**
     * 优化方式:将之前计算的数据存入数组中，防止重复计算
     * @param n 求哪一项的值
     * @return 目标值
     */
    public static int fibonacci2(int n) {
        // 从0开始，所以数组容量为n+1
        int[] cache = new int[n + 1];
        // 使用-1先将数组填充
        Arrays.fill(cache, -1);
        // 为两个初始值赋值
        cache[0] = 0;
        cache[1] = 1;
        return f(n, cache);
    }

    /**
     * 先查询缓存，没有再进行计算
     * @param n 求哪一项的值
     * @param cache 缓存数组
     * @return 目标值
     */
    public static int f(int n, int[] cache) {
        if (cache[n] != -1) {
            return cache[n];
        }

        int x = f(n - 1,cache);
        int y = f(n - 2,cache);

        cache[n] = x + y; // [0,1,?,-1,-1] 存入数组
        return cache[n];
    }
}
